<?php
/**
 * Created by PhpStorm.
 * User: allen
 * Date: 2019/2/18
 * Time: 10:26 PM
 */

// 快速排序采用分治法实现排序，具体步骤：
// 1、从数列中挑出一个数作为基准元素。通常选择第一个或最后一个元素。
// 2、扫描数列，以基准元素为比较对象，把数列分成两个区。规则是：小的移动到基准元素前面，大的移到后面，相等的前后都可以。分区完成之后，基准元素就处于数列的中间位置。
// 3、然后再用同样的方法，递归地排序划分的两部分。

//原地排序版本，不需要额外的存储空间：
function partition(&$arr, $leftIndex, $rightIndex)
{
    $pivot = $arr[($leftIndex + $rightIndex) / 2];

    while ($leftIndex <= $rightIndex) {
        while ($arr[$leftIndex] < $pivot) {
            $leftIndex++;
        }

        while ($arr[$rightIndex] > $pivot) {
            $rightIndex--;
        }

        if ($leftIndex <= $rightIndex) {
            list($arr[$leftIndex], $arr[$rightIndex]) = [$arr[$rightIndex], $arr[$leftIndex]];

            $leftIndex++;
            $rightIndex--;
        }
    }

    return $leftIndex;
}

function quickSort(&$arr, $leftIndex, $rightIndex)
{
    if ($leftIndex < $rightIndex) {
        $index = partition($arr, $leftIndex, $rightIndex);

        quickSort($arr, $leftIndex, $index - 1);
        quickSort($arr, $index, $rightIndex);
    }
}

$arr = [0,3,-1,10,5,20];
$arr = quickSort($arr);
print_r($arr);